package com.yww.algorithm.binarysearch;

/**
 * @author yww
 * @description 二分查找
 * @since 2024/1/28 17:22
 */
public class BinarySearch {
    public static int binarySearch01(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int m;
        while (i <= j) {
//            m = (i + j) >>> 1;
            m = i + ((j - i) >> 1);
            if (arr[m] > target) {
                j = m - 1;
            } else if (arr[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }


    public static int binarySearch02(int[] arr, int target) {
        int i = 0, j = arr.length;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m;
            } else if (arr[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    // 平衡版
    public static int binarySearch03(int[] arr, int target) {
        int i = 0, j = arr.length;
        while (j - i > 1) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m;
            } else {
                i = m;
            }
        }

        if (arr[i] == target) {
            return i;
        }
        return -1;
    }

    // leftmost
    public static int binarySearch04(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else if (arr[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    // rightmost
    public static int binarySearch05(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else if (arr[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }


    // leftmost application 返回 >= target 的最靠左索引
    public static int binarySearch06(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= arr[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    // rightmost application 返回 <= target 的最靠右索引
    public static int binarySearch07(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i - 1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 55, 78, 78, 78, 96, 231};
        System.out.println(binarySearch01(arr, 78));
        System.out.println(binarySearch02(arr, 78));
        System.out.println(binarySearch03(arr, 78));
        System.out.println(binarySearch04(arr, 78));
        System.out.println(binarySearch05(arr, 78));
        System.out.println(binarySearch06(arr, 78));
        System.out.println(binarySearch07(arr, 78));
        System.out.println(Integer.MAX_VALUE);
    }
}
